package NO3_LinkedList;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 2025-08-29
 * 力扣 - 19. 删除链表的倒数第 N 个结点
 * <p>
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class RemoveNthFromEndMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(
                1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(5)))));
        ListNode head1 = new ListNode(
                1,
                new ListNode(2));
        ListNode.printList(removeNthFromEnd(head, 2));
        ListNode.printList(removeNthFromEnd(head1, 1));
    }

    // 新建链表
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 1.创建一个链表，添加链表所有新节点
        ArrayList<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(new ListNode(head.val));
            head = head.next;
        }
        // 2.删除倒数第n个节点
        if (n > 0 && n <= list.size()) {
            list.remove(list.size() - n);
        }
        // 3.链表重新连接
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).next = list.get(i + 1);
        }
        // 设置尾节点为null
        if (!list.isEmpty()) {
            list.get(list.size() - 1).next = null;
        }
        // 5.返回头节点
        return list.isEmpty() ? null : list.get(0);
    }

    // 使用栈
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        // 创建哑节点，简化边界条件处理（比如删除头节点）
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 创建栈来存储节点
        Stack<ListNode> stack = new Stack<>();
        ListNode current = dummy;

        // 第一步：所有节点入栈（包括哑节点）
        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        // 第二步：弹出n个节点
        for (int i = 0; i < n; i++) {
            stack.pop();
        }

        // 第三步：此时栈顶节点就是要删除节点的前一个节点
        ListNode prev = stack.peek();

        // 第四步：删除倒数第n个节点
        prev.next = prev.next.next;

        // 第五步：返回结果（跳过哑节点）
        return dummy.next;
    }
}
